#ifndef _BT_H_
#define _BT_H_

#define OK 1
#define ERROR 0
#define OVERFLOW -2

#define COMMENT 0

typedef int    Status;
typedef char   ElemType;

typedef struct TNode {
    ElemType data;
    struct TNode *left, *right;
}TNode, *BTree;

typedef enum {Link, Thread} PointerThr;
typedef struct ThrTNode {
    ElemType data;
    struct ThrTNode *left, *right;
    PointerThr ltag, rtag;      
}ThrTNode, *TBTree;

#if COMMENT
/**
 * CreateBiTree_pre functions as follows:
 * create a binary tree by input the preorder traversal result
 */
Status CreateBiTree_Pre(BTree *B);
#endif

/**
 * @brief InitBiTree functions as follows:
 * initialize the BTree B with NULL
 */
Status InitBiTree(BTree *t);

/**
 * @brief PreCreateBiTree functions as follows:
 * create a binary tree by input the preorder traversal result
 * 'Z' is used to repersent empty node
 * an example input: "aZZ", where a is the root of the tree with no children
 */
BTree PreCreateBiTree(void);

/**
 * @brief   print the bitree by preorder
 * @author  MiaoHao-oops
 */
void PreTraverse(const BTree t);

/**
 * @brief   print the bitree by inorder
 * @author  MiaoHao-oops
 */
void InTraverse(const BTree t);

/**
 * @brief   print the bitree by postorder
 * @author  MiaoHao-oops
 */
void PostTraverse(const BTree t);

/**
 * @brief   inorder threading the binary tree
 * @author  MiaoHao-oops
 */
TBTree InThrBiTree(BTree t);
void InorderThreading(TBTree t, ThrTNode **pre);
TBTree CopyBiTree(BTree t);
#endif
